/**
 * 给定一个二维数组，某人从左上走到右下，再走回来
 * 问来回获取的最大权值是多少
 * 网格为-1表示障碍，为0或1表示相应的权值
 * 每个格子的权值取完就变成0，即如果回程还走这一格就没有收益。
 * 
 * 注意到来回是两条路，因此可以等价于两个人同时走一次
 * 设 Dijuv 是一人在(i,j)、一人在(u,v)时的最大收益
 * 且两人肯定是同步行进的，因此 Dijuv由4种可能性决定
 * 分别是 (i-1,j)(i,j-1) × (u-1,v)(u,v-1)
 * 注意到这是一个四重循环，实际上考虑到 i+j == u+v 因此只要三重循环即可
 * 
 */
using vi = vector<int>;
using vvi = vector<vi>;

int const XX[2][2] = {
    {-1, 0},
    {0, -1}
};

int N, M;
vector<vector<vvi>> D;

void chkmax(int & d, int a){
    if(-1 == a) return;
    if(-1 == d or d < a) d = a;
}

void chkaddass(int & d, int a){
    assert(a != -1);
    if(-1 == d) return;
    d += a;
}

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        N = grid.size();
        M = grid[0].size();

        D.assign(N, vector<vvi>(M, vvi(N, vi(M, -1))));
        D[0][0][0][0] = grid[0][0];

        for(int i=0;i<N;++i)for(int j=0;j<M;++j){
            if(0 == i and 0 == j) continue;
            if(-1 == grid[i][j]) continue;

            for(int u=0;u<N;++u)for(int v=0;v<M;++v){
                if(0 == u and 0 == v) continue;
                if(-1 == grid[u][v]) continue;

                auto & d = D[i][j][u][v];

                for(const auto & ax : XX){
                    int x0 = ax[0] + i;
                    int y0 = ax[1] + j;
                    if(x0 < 0 or x0 >= N) continue;
                    if(y0 < 0 or y0 >= M) continue;
                    for(const auto & bx : XX){
                        int x1 = bx[0] + u;
                        int y1 = bx[1] + v;
                        if(x1 < 0 or x1 >= N) continue;
                        if(y1 < 0 or y1 >= M) continue;    

                        chkmax(d, D[x0][y0][x1][y1]);      
                    }
                }
                if(i == u and j == v) chkaddass(d, grid[i][j]);
                else chkaddass(d, grid[i][j] + grid[u][v]);
            }
        }

        if(-1 == D[N-1][M-1][N-1][M-1]) return 0;
        return D[N-1][M-1][N-1][M-1];
    }
};